package com.mccken.practice.top100.Top_1$20.top_2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2023-12-28 10:34
 **/
public class GroupAnagrams {

	/**
	 * 时间复杂度 O(nklogk)
	 */
	public List<List<String>> groupAnagrams(String[] strs) {
		Map<String, List<String>> map = new HashMap<>();
		for (String str : strs) {
			int[] counts = new int[26];
			int length = str.length();

			for (int i = 0; i < length; i++) {
				counts[str.charAt(i) - 'a']++;
			}

			//将每个出现次数大于0的字母和出现的次数按顺序进行排列，拼接沉成字符串，作为哈希表的键
			// a2r3s2  s3w2a4  并没有排序        
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < 26; i++) {
				if (counts[i] != 0) {
					// 出现的字母
					char _char = (char) ('a' + i);
					sb.append(_char);
					sb.append(counts[i]);
				}
			}

			String key = sb.toString();
			map.putIfAbsent(key, new ArrayList<String>());
			map.get(key).add(str);
		}
		return new ArrayList<>(map.values());
	}

	public List<List<String>> groupAnagrams2(String[] strs) {

		HashMap<String, List<String>> map = new HashMap<>();
		for (String s : strs) {
			char[] chars = s.toCharArray();
			Arrays.sort(chars);
			String key = String.valueOf(chars);
			map.putIfAbsent(key, new ArrayList<>());
			map.get(key).add(s);
		}
		return new ArrayList<>(map.values());
	}

	public static void main(String[] args) {
		String[] strs = new String[]{"eat", "tea", "tan", "ate", "nat", "bat"};
		GroupAnagrams groupAnagrams = new GroupAnagrams();
		System.out.println(groupAnagrams.groupAnagrams(strs));
	}
}
